home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
FishMarket 1.0
/
FishMarket v1.0.iso
/
fishies
/
501-525
/
disk_519
/
avlsort
/
avl
/
avl.c
next >
Wrap
C/C++ Source or Header
|
1992-05-06
|
14KB
|
499 lines
/* avl.c AVL routines
Copyright 1988 Zinn Computer Company
by Mark E. Mallett
All rights reserved;
This software may be used at will, provided that all credits
and style be left in place, and that its distribution is not restricted.
Bug fixes and improvements are welcomed, please send these back to
me at mem@zinn.MV.COM
This is a general-purpose implementation of AVL trees in C.
It is derived from the description of AVL (Adelson-Velskii and Landis)
trees found in Knuth's "The Art of Computer Programming Volume 3:
Searching and Sorting" (Addison-Wesley, 1973) pgs 451-471.
The routines in this file deal with tree maintenance only.
These routines are only concerned with the arrangement of the nodes
in the tree. Composition of those nodes is left to outside knowledge.
The caller must construct an AVL tree header structure which specifies
routines that deal with nodes (comparison, construction, and deletion).
Please see the attached document for further information.
Contained in this file:
avlfind Find a node in an AVL tree
avldelete Delete a node from an AVL tree
avlinsert Insert a node into an AVL tree
*/
#include <stdio.h>
#include "avl.h"
/* Local definitions */
/* External routines */
/* External data */
/* Local routines */
/* Local data */
/*
*//* avlfind( treeP, keyP )
Lookup a value in an avl tree
Accepts :
treeP Address of the AVLTREE structure describing the tree.
keyP Address of a key for the node. Interpretation of
the key is left to the "compare key" routine.
Returns :
<value> The address of the node if it is found,
NULL if it is not.
*/
AVLNODE *
avlfind( treeP, keyP )
AVLTREE *treeP; /* Address of the tree struct */
void *keyP; /* Address of the key info */
{
AVLNODE *nodeP; /* To follow the tree with */
/* Traverse the tree until the node is found or the tree runs out. */
for( nodeP = treeP->t_rootP; nodeP != NULL; ) {
switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
case 0: /* Node found! */
return( nodeP ); /* Go ahead and return it */
case -1: /* Take left branch */
nodeP = nodeP->n_leftP;
break;
case 1: /* Take right branch */
nodeP = nodeP->n_rightP;
break;
}
}
/* Didn't find the node in the tree. */
return( NULL );
}
/*
*//* avlinsert( treeP, keyP, dataP )
Insert a node in an avl tree
Accepts :
treeP The address of the tree header structure.
keyP The address of the key for the node. Interpretation
of the key is by the compare and node-create
routines specified in the avl tree header.
dataP The address of the data info for the tree. The
interpretation of this is left to the create-node
routine specified in the avl tree header.
Returns :
<value> -1 if failure of some kind
0 if successful insertion
1 if duplicate key
Notes:
The tree header structure specifies a node construction routine
that is responsible for allocating a node and putting the new
key and data information into it. It is called as follows:
nodeP = construct( treeP, keyP, dataP, enodeP )
treeP, keyP, and dataP are as passed to this routine. "enodeP"
is NULL if a new node is required; otherwise it is the address
of an already existing node that matches the specified key -
in this case it is up to the constructor to decide whether to
overwrite the existing node or to call it an error. The routine
is expected to return the address of the AVLNODE structure
that is allocated (if enode==NULL ) or that exists, or to
return NULL if the node is not made (or used).
*/
int
avlinsert( treeP, keyP, dataP )
AVLTREE *treeP; /* Addr of the tree struct */
void *keyP; /* The key for insertion insert */
void *dataP; /* The data for the insertion */
{
int direction; /* Direction we took from decision pt */
AVLNODE *nodeP; /* Node that we're looking at */
AVLNODE *clearP; /* For erasing tracks */
AVLNODE **nodePP; /* Pointer to the next link */
AVLNODE **topPP; /* Pointer to the top pointer */
/* Traverse the tree to find an insertion point (or existing key).
Along the way, we'll adjust the balance counts on the nodes as
we pass by them. And as we do this, we'll remember the potential
tree rotation point (the lowest non-balanced treetop) as well as
the direction we took from it (in case we have to fix it up when
we discover a lower balance point). */
nodePP = topPP = &(treeP->t_rootP); /* Start at top of tree */
direction = 0; /* Haven't gone anywhwere yet */
while( (nodeP = *nodePP) != NULL ) { /* Till we reach the end */
/* See if we're at a potential balance point */
if ( nodeP->n_balance != 0 ) {
/* New balance point. Erase any trail we've made to here */
if ( direction != 0 )
for( clearP = *topPP; clearP != nodeP;
direction = clearP->n_balance ) {
clearP->n_balance -= direction;
if ( direction < 0 )
clearP = clearP->n_leftP;
else
clearP = clearP->n_rightP;
}
direction = 0; /* So we make new balance point */
topPP = nodePP; /* Remember new top */
}
/* Now follow the tree... */
switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
case 0: /* Match */
/* Here we have a duplicate node. First erase the
trail that we left. */
if ( direction != 0 )
for( clearP = *topPP; clearP != NULL;
direction = clearP->n_balance ) {
clearP->n_balance -= direction;
if ( direction < 0 )
clearP = clearP->n_leftP;
else
clearP = clearP->n_rightP;
}
/* Give the node to the node constructor and
see what we get. */
if ( (*treeP->t_mknode)( treeP, keyP, dataP, nodeP ) == NULL )
return( 1 ); /* Duplicate key */
return( 0 ); /* Return success */
case -1: /* Go left */
nodePP = &(nodeP->n_leftP);
--nodeP->n_balance;
if ( direction == 0 ) /* Remember balance point branch? */
direction = -1;
break;
case 1: /* Go right */
nodePP = &(nodeP->n_rightP);
++nodeP->n_balance;
if ( direction == 0 )
direction = 1;
break;
}
}
/* Here we've gotten to the bottom, so make a new node */
nodeP = (*treeP->t_mknode)( treeP, keyP, dataP, (AVLNODE *)NULL );
if ( nodeP != NULL ) { /* Successful node creation? */
nodeP->n_balance = 0; /* Fill in the nitty gritty */
nodeP->n_leftP = nodeP->n_rightP = NULL;
*nodePP = nodeP; /* Link it in */
balance( topPP ); /* May need reshaping now */
return( 0 ); /* Return success */
}
/* Error making node. Erase our trail */
if ( direction != 0 )
for( clearP = *topPP; clearP != NULL;
direction = clearP->n_balance ) {
clearP->n_balance -= direction;
if ( direction < 0 )
clearP = clearP->n_leftP;
else
clearP = clearP->n_rightP;
}
return( -1 ); /* Return error */
}
/*
*//* avldelete( treeP, keyP )
Delete a node from an AVL tree
Accepts:
treeP Address of the tree definition structure.
keyP Address of the key for the node. Interpretation
of the key is left to the key-compare routine
specified in the tree header.
Returns :
<value> 0 if deleted OK
-1 if not found
*/
int
avldelete( treeP, keyP )
AVLTREE *treeP; /* Addr of tree block */
void *keyP; /* Addr of key */
{
/* Simply call a local deletion routine */
if ( delete( treeP, &treeP->t_rootP, keyP ) < 0 )
return( -1 ); /* error in delete */
return( 0 ); /* Fine and dandy */
}
/*
*//* delete( treeP, topPP, keyP )
Local routine to delete from a subtree
Accepts:
treeP Address of the tree definition structure
topPP Address of the pointer to this branch
keyP Address of the key for the node. Interpretation
of the key is left to the key-compare routine
specified in the tree header.
Returns :
<value> -1 if not found;
0 if deleted and tree did not shrink;
1 if deleted and tree shrunk by 1.
*/
static int
delete( treeP, topPP, keyP )
AVLTREE *treeP; /* Addr of tree block */
AVLNODE **topPP; /* Addr of ptr to branch */
void *keyP; /* Addr of key */
{
int i; /* Scratch */
int sts;
int cmp; /* Comparison result */
AVLNODE *nodeP; /* Node pointer */
AVLNODE *node1P; /* Another one */
AVLNODE *tempP; /* For exchanging */
AVLNODE **linkPP; /* Addr of a node pointer */
nodeP = *topPP; /* Get addr of node */
if ( nodeP == NULL ) /* If we hit bottom */
return( -1 ); /* then we didn't find it */
cmp = (*treeP->t_cmprtc)( keyP, nodeP );
if ( cmp == 0 ) {
/* We've found the node to delete. If it has no children we
can just get rid of it. Otherwise we have to remove it
from the tree somehow. If one or the other subtrees
is empty, then it is easy. */
if ( nodeP->n_leftP == NULL ) {
/* Just shorten the right branch (even if it doesn't exist) */
*topPP = nodeP->n_rightP;
(*treeP->t_rmnode)( treeP, nodeP );
return( 1 ); /* Branch shrunk */
}
if ( nodeP->n_rightP == NULL ) {
/* Shorten the left branch */
*topPP = nodeP->n_leftP;
(*treeP->t_rmnode)( treeP, nodeP );
return( 1 );
}
/* Both subtrees exist. Exchange this node with the one
logically adjacent (in value) to it. Then this node
will be at the end of a branch and we can recurse to
delete it. */
if( nodeP->n_balance < 0 ) {
node1P = nodeP->n_leftP;
linkPP = &(node1P->n_leftP);
for( ; node1P->n_rightP != NULL; node1P = node1P->n_rightP )
linkPP = &(node1P->n_rightP);
cmp = -1; /* We went left */
} else {
node1P = nodeP->n_rightP;
linkPP = &(node1P->n_rightP);
for( ; node1P->n_leftP != NULL; node1P = node1P->n_leftP )
linkPP = &(node1P->n_leftP);
cmp = 1; /* We're going right */
}
/* Exchange the two nodes. We have to actually exchange by
relinking rather than copying since the node may imply
other stuff that we don't know about here. */
tempP = node1P->n_rightP; /* Exchange right pointers */
node1P->n_rightP = nodeP->n_rightP;
nodeP->n_rightP = tempP;
tempP = node1P->n_leftP; /* Exchange left pointers */
node1P->n_leftP = nodeP->n_leftP;
nodeP->n_leftP = tempP;
i = node1P->n_balance; /* Exchange balance values */
node1P->n_balance = nodeP->n_balance;
nodeP->n_balance = i;
*topPP = node1P; /* Exchange the nodes */
*linkPP = nodeP;
nodeP = node1P; /* Pretend we're here */
}
/* Remove the node from left or right subtree depending on "cmp" */
switch ( cmp ) {
case -1:
sts = delete( treeP, &nodeP->n_leftP, keyP );
if ( sts == 1 ) /* If it shrunk */
++nodeP->n_balance; /* reflect that in the balance */
break;
case 1:
sts = delete( treeP, &nodeP->n_rightP, keyP );
if ( sts == 1 ) /* Right branch shrunk? */
--nodeP->n_balance; /* adjust the balance */
break;
}
if ( sts == 1 ) /* If we changed balance */
if ( nodeP->n_balance != 0 ) /* if it's 0 it shrunk but is ok */
sts = balance( topPP ); /* otherwise fix it up */
return( sts );
}
/*
*//* balance( branchPP )
Local routine to balance a branch
Accepts :
branchPP Addr of the variable pointing to the top n
Returns :
<value> 0 if branch has stayed the same height;
1 if branch shrunk by one.
Notes :
This routine accepts a branch in conditions left by the
internal routines only. No other cases are dealt with.
*/
static int
balance( branchPP )
AVLNODE **branchPP; /* Ptr to top node */
{
int shrunk; /* Whether we shrunk */
AVLNODE *nodeP; /* Current top node */
AVLNODE *leftP; /* Left child */
AVLNODE *rightP; /* Right child */
AVLNODE *migP; /* A ndoe that migrates */
/* Pick up relevant information */
nodeP = *branchPP;
leftP = nodeP->n_leftP;
rightP = nodeP->n_rightP;
shrunk = 0; /* Assume tree doesn't shrink */
/* Process according to out-of-balance amount, if any */
switch( nodeP->n_balance ) {
case -2: /* Too heavy on left */
if ( leftP->n_balance <= 0 ) {
/* Single rotation */
*branchPP = leftP;
nodeP->n_leftP = leftP->n_rightP;
leftP->n_rightP = nodeP;
++leftP->n_balance;
nodeP->n_balance = -(leftP->n_balance);
if ( leftP->n_balance == 0 )
shrunk = 1;
}
else { /* Migration of inner node to top */
migP = leftP->n_rightP;
leftP->n_rightP = migP->n_leftP;
nodeP->n_leftP = migP->n_rightP;
migP->n_leftP = leftP;
migP->n_rightP = nodeP;
*branchPP = migP;
if ( migP->n_balance < 0 ) {
leftP->n_balance = 0;
nodeP->n_balance = 1;
}
else if ( migP->n_balance > 0 ) {
leftP->n_balance = -1;
nodeP->n_balance = 0;
}
else
leftP->n_balance = nodeP->n_balance = 0;
migP->n_balance = 0;
shrunk = 1;
}
break;
case 2: /* Too heavy on right */
if ( rightP->n_balance >= 0 ) {
/* Single rotation */
*branchPP = rightP;
nodeP->n_rightP = rightP->n_leftP;
rightP->n_leftP = nodeP;
--rightP->n_balance;
nodeP->n_balance = -(rightP->n_balance);
if ( rightP->n_balance == 0 )
shrunk = 1;
}
else { /* Migration of inner node */
migP = rightP->n_leftP;
rightP->n_leftP = migP->n_rightP;
nodeP->n_rightP = migP->n_leftP;
migP->n_leftP = nodeP;
migP->n_rightP = rightP;
*branchPP = migP;
if ( migP->n_balance < 0 ) {
nodeP->n_balance = 0;
rightP->n_balance = 1;
}
else if ( migP->n_balance > 0 ) {
nodeP->n_balance = -1;
rightP->n_balance = 0;
}
else
nodeP->n_balance = rightP->n_balance = 0;
migP->n_balance = 0;
shrunk = 1;
}
}
return( shrunk );
}